package com.echo.boot.structure.tree.binarytree;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/5/25
 * Time: 6:53
 *
 * @author Administrator
 */
public class RedBlackTree<E> extends BalancedBinarySearchTree<E> {
    /**
     * 红色
     */
    private static final boolean RED = false;
    /**
     * 黑色
     */
    private static final boolean BLACK = true;

    private Comparator<E> comparator;

    public RedBlackTree() {
        this(null);
    }

    public RedBlackTree(Comparator<E> comparator) {
        super(comparator);
    }

    private static class RedBlackNode<E> extends Node<E> {
        private boolean color = RED;

        public RedBlackNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            String parentString = null;
            String color = null;
            if (parent != null) {
                parentString = parent.element.toString();
            }
            if (this.color) {
                color = "black";
            } else {
                color = "red";
            }
            return element + "_p(" + parentString + ")_color(" + color + ")";
        }
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RedBlackNode<>(element, parent);
    }

    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;

        // 添加的是根节点,上溢到了根节点
        if (parent == null) {
            black(node);
            return;
        }
        // 父节点是黑色,直接返回
        if (isBlack(parent)) {
            return;
        }
        //uncle 节点判断
        Node<E> uncle = parent.sibling();
        // 祖父节点
        Node<E> grand = parent.parent;
        // 红黑树 与 4 阶 B 树等价
        // 如果uncle节点是红色,就出现上溢,出现上溢中间节点上移,分裂出2个子节点,最高的情况一直上溢到根节点
        // 保证红黑树属性,子节点必须为黑色(因为只有黑色才能独立一个子节点)
        // 向上移动的节点,当成一个新添加的节点,上移,再次重复此操作。
        // 上溢的情况(也就是添加的时候uncle 是红色的时候)
        if (isRed(uncle)) {
            black(parent);
            black(uncle);
            red(grand);
            afterAdd(grand);
            return;
        }
        // uncle 不是 红色
        // L
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) {
                //LL
                black(parent);
                red(grand);
                rotateRight(grand);
            } else {
                //LR
                black(node);
                red(grand);
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {
            // R
            if (node.isLeftChild()) {
                // RL
                black(node);
                red(grand);
                rotateRight(parent);
                rotateLeft(grand);
            } else {
                // RR
                black(parent);
                red(grand);
                rotateLeft(grand);
            }
        }
    }

    @Override
    protected void afterRemove(Node<E> node) {
        // 如果删除的节点是红色
        // 或者 用以取代删除节点的子节点是红色
        if (isRed(node)) {
            black(node);
            return;
        }

        Node<E> parent = node.parent;
        // 删除的是根节点
        if (parent == null) {
            return;
        }

        // 删除的是黑色叶子节点【下溢】
        // 判断被删除的node是左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if (left) { // 被删除的节点在左边，兄弟节点在右边
            if (isRed(sibling)) { // 兄弟节点是红色
                black(sibling);
                red(parent);
                rotateLeft(parent);
                // 更换兄弟
                sibling = parent.right;
            }

            // 兄弟节点必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                // 兄弟节点的左边是黑色，兄弟要先旋转
                if (isBlack(sibling.right)) {
                    rotateRight(sibling);
                    sibling = parent.right;
                }

                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }
        } else { // 被删除的节点在右边，兄弟节点在左边
            if (isRed(sibling)) { // 兄弟节点是红色
                black(sibling);
                red(parent);
                rotateRight(parent);
                // 更换兄弟
                sibling = parent.left;
            }

            // 兄弟节点必然是黑色
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if (parentBlack) {
                    afterRemove(parent);
                }
            } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
                // 兄弟节点的左边是黑色，兄弟要先旋转
                if (isBlack(sibling.left)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }

                color(sibling, colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) {
            return node;
        }
        ((RedBlackNode<E>) node).color = color;
        return node;
    }

    private Node<E> red(Node<E> node) {
        return color(node, RED);
    }

    private Node<E> black(Node<E> node) {
        return color(node, BLACK);
    }

    private boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RedBlackNode<E>) node).color;
    }

    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }


}
